package com.tgy.algorithm.base._图_02;

import java.util.*;

public class Graph <V>{
    HashMap<V,Node<V>> nodes;
    HashSet<Edge<V>> edges;

    public Graph() {
        this.nodes = new HashMap<>();
        this.edges = new HashSet<>();
    }


    public static <V> Graph<V> createGraph(V[][] nums) {

        Graph<V> vGraph = new Graph<>();

        for (V[] num : nums) {
            V from = num[0];
            V to = num[1];
            V value = num[2];
            if (!vGraph.nodes.containsKey(from)) {
                vGraph.nodes.put(from,new Node<>(from));
            }
            if (!vGraph.nodes.containsKey(to)) {
                vGraph.nodes.put(to,new Node<>(to));
            }
            Node<V> fromNode = vGraph.nodes.get(from);
            Node<V> toNode = vGraph.nodes.get(to);
            Edge<V> vEdge = new Edge<V>(value,fromNode,toNode);
            fromNode.out++;
            fromNode.nexts.add(toNode);
            fromNode.edges.add(vEdge);
            toNode.in++;

            vGraph.edges.add(vEdge);
        }

        return vGraph;
    }

    // depth first search
    public static <V> void dfs(Node<V> node) {

        Stack<Node<V>> stack = new Stack<>();
        HashSet<Node<V>> visitSet = new HashSet<>();

        stack.push(node);
        visitSet.add(node);
//        System.out.println(node.value);

        while (!stack.isEmpty()) {
            Node<V> tmpNode = stack.pop();
//            visitSet.add(tmpNode);
            System.out.println(tmpNode.value);
            for (Node<V> next : tmpNode.nexts) {
                if (!visitSet.contains(next)) {
                    stack.push(next);
                    visitSet.add(next);
                }
            }
        }
    }


    // 广度遍历 breadth first search
    public static <V> void bfs(Node<V> node) {
        LinkedList<Node<V>> queue = new LinkedList<>();
        HashSet<Node<V>> visitSet = new HashSet<>();

        queue.offer(node);
        visitSet.add(node);
        while (!queue.isEmpty()) {
            Node<V> tmpNode = queue.poll();
            System.out.println(tmpNode.value);
            for (Node<V> next : tmpNode.nexts) {
                if (!visitSet.contains(next)) {
                    queue.offer(next);
                    visitSet.add(next);
                }
            }
        }
    }

    public static <V> void bfs01(Node<V> node) {
        LinkedList<Node<V>> queue = new LinkedList<>();
        HashSet<Node<V>> visitSet = new HashSet<>();
        queue.offer(node);
        visitSet.add(node);
        System.out.println(node.value);
        while (!queue.isEmpty()) {
            Node<V> tmpNode = queue.poll();
            for (Node<V> next : tmpNode.nexts) {
                if (!visitSet.contains(next)) {
                    queue.offer(tmpNode);
                    queue.offer(next);
                    visitSet.add(next);
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }

    /**
     *
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        Integer[][] nums = {{0,1,3},{0,2,4},{1,2,3},{2,3,2},{2,4,1},{1,3,4}};
        Graph<Integer> graph = createGraph(nums);
        System.out.println(graph);
//        dfs(graph.nodes.get(0));
        bfs01(graph.nodes.get(0));
    }
}
